/**
 * 项目名称: Topic_501.cpp
 * 项目路径: study/DataStructure/LeetCode/树/简单
 * 编辑时间: 2024年08月21日08时30分11秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 暴力做法
//class Solution {
//public:
//    int offset = 1e5;
//    int p[200010];
//    vector<int>ans;
//    void pre(TreeNode* root){
//        if(root){
//            p[root->val+offset]++;
//            pre(root->left);
//            pre(root->right);
//        }
//    }
//    vector<int> findMode(TreeNode* root) {
//        if(!root)return ans;
//        int max_=0;
//        pre(root);
//        for(auto x:p)if(x>max_)max_=x;
//        for(int i = 0 ;i<200010;i++)
//            if(p[i] == max_)ans.push_back(i-offset);
//        return ans;
//    }
//};
class Solution {
public:
    vector<int>ans;
    int base,count,MaxCount;
    void update(int x){
        if(x == base){
            ++count;
        }else{
            count = 1;
            base = x;
        }

        if(count == MaxCount){
            ans.push_back(base);
        }

        if(count > MaxCount){
            MaxCount = count;
            ans = vector<int>{base};
        }
    }

    void In(TreeNode* root){
        if(!root)return;
        In(root->left);
        update(root->val);
        In(root->right);
    }

    vector<int> findMode(TreeNode* root) {
        In(root);
        return ans;
    }
};
